The present invention concerns apparatus and a method for decoding data which has been encoded for error detection and correction using a cross-interleaved Reed-Solomon code, and in particular, to a Reed-Solomon decoder which performs a reduced number of computations compared to conventional decoding methods.
Compact disk read-only memory (CD-ROM) computer peripheral devices, based on compact disk (CD) audio players have been available for many years. These devices recover recorded digital data from a compact disk. CD-ROM data, recorded on the compact disk, is in a different format than audio information. The different format is needed because the recording of digital data on the compact disk must meet requirements that did not need to be addressed when data representing audio signals was recorded on the disk, namely, the ability to recover the data with a very low error rate.
The error rate for audio data may be higher than for general digital data because conventional error concealment techniques may be used effectively for audio data. These techniques assume that the data is changing slowly with respect to the sample rate; that each data value can be reconstructed as some function of the data values that surround it. An exemplary error concealment technique would be to infer the value of an erroneous audio sample by interpolating between two adjacent correct samples.
This redundancy cannot be relied upon, however to recover digital data from a CD-ROM device. While there may be some redundancy if the data is audio data or video data, there is generally no redundancy in other types of data that may be recorded on a CD-ROM device, such as an encyclopedia article or a tables of values.
To ensure accurate reproduction of the data recorded on a CD-ROM, therefore, the data is encoded using a complex error correcting code known as an cross-interleaved Reed-Solomon (CIRS) code before it is recorded.
Details on the data format used to record data on CD-ROMs may be found in U.S. Pat. No. 4,998,252 entitled, METHOD AND APPARATUS FOR TRANSMITTING DIGITAL DATA which is hereby incorporated by reference for its teachings on CD-ROM data decoding techniques.
FIG. 1 (prior art) is a data structure diagram of a CD-ROM data sector. As shown in this Figure, each sector includes seven data fields: a SYNCH field, a HEADER field, a DATA field, an Error Detection Code (EDC) field, an empty (SPACE) field, a P-PARITY field and a Q-PARITY field.
As shown in FIG. 2 (prior art), the SYNCH field includes a first zero-value byte followed by 10 bytes of all-ones and then, another zero-valued byte. The HEADER field includes four one-byte subfields. The first two of these, MIN and SEC, give the absolute time displacement of the sector from the beginning of the disk if the sectors were replayed sequentially. This may be used as an address to locate the sector. The next byte, SECTOR, uniquely identifies the sector and a final byte, MODE, describes the type of data that is recorded in the sector. This byte is used in an audio CD to signal the player that the data is in audio format and it is used in a CD-ROM device to indicate that the data is in CD-ROM format.
After the header, the remaining data values in the sector are identified as bytes from byte D0001 to byte D2336. Referring to FIG. 1, some of these are user data bytes and others are the EDC, SPACE, P PARITY AND Q PARITY fields of the sector.
As shown in FIG. 2, each sector may be divided into two parts, one (R-ch) which holds 16-bit right-channel data and one (L-ch) which holds 16-bit left-channel data. This terminology is a remnant of the audio CD data format; data in a CD-ROM sector may be split across the left and right channels. The data values stored on a CD-ROM are 16-bit values, having a most significant byte (MSB) and a least significant byte (LSB). As described below, one of the data scrambling techniques used to effectively compensate for errors which affect a block of adjacent data values is to apply the error correcting codes (i.e. P PARITY and Q PARITY) separately to the MSB's and to the LSB's. In the materials that follow, the MSB values of a sector are referred to as being in the MSB plane and the LSB values are referred to as being in the LSB plane.
FIG. 3 (prior art) is a data structure diagram of a matrix 310 which illustrates the process of applying the error correcting codes to one of these planes. As shown in FIG. 3, the header and user data information in this plane occupy 1032 bytes (bytes 0 through 1031). These bytes are arranged in a matrix of 24 rows by 43 columns. As shown in the Figure, an individual P PARITY value is generated from data values (i.e. a P sequence) taken along one columns of the matrix as illustrated by the arrow 310. In the same way, each of the Q PARITY values is generated from a sequence of values (i.e. a Q sequence) taken along a matrix diagonal, as illustrated by the arrow 312.
The P PARITY values include 86 bytes which relate to the 43 matrix columns as shown in FIG. 3 (i.e. 2 bytes per column). The Q PARITY values include 52 bytes, each pair of bytes generated from 43 values taken along a respectively different one of 26 matrix diagonals.
Both the P PARITY and Q PARITY values, hereinafter referred to collectively as the P series and Q series, respectively, are generated using Reed-Solomon codes. The particular code used to generate the P series is a (26,24) code over a Galois field of 256 (i.e. GF (256)) . The generating polynomial for GF (256) is x.sup.8 +x.sup.4 +x.sup.3 +x.sup.2 +1 and the primitive element .alpha. of GF(256) is given by the vector (0,0,0,0,0,0,1,0) over GF(2), most significant bit to least significant bit. This code corrects 1 GF(256) error and detects 2 GF(256) errors. The parity check matrix HP is given by equation (1) ##EQU1##
The parity check matrix HP is applied a set of vectors, VP(i), representing respectively different columns the matrix shown in FIG. 25. The column vector is multiplied by the parity check matrix to produce a syndrome SP(i) according to equation (2). EQU SP(i)=HP.times.VP(i) (2)
If the value of the syndrome SP(i) is zero, there are either no errors in the column i or there are more than two errors. If the syndrome is non-zero it may indicate a bit location in the corresponding column of bytes has a one-bit error, which can be corrected, or a multi-bit error, which cannot. While the syndrome may have a zero value for some sets of three or more errors in a column, it may also have a non-zero value. All columns having two erroneous bits will produce a non-zero syndrome.
The Q series is generated from a (45,43) Reed Solomon code over GF(256). This code also corrects 1 and detects 2 GF(256) errors. The parity check matrix, HQ, is given by equation (3). ##EQU2##
As described above, the Q codes are generated from values along the diagonals of the matrix of digital values. This matrix 310 includes the header and user data values from the sector 110 and the P PARITY values.
If the Q PARITY values are removed from the matrix 310 and each column, 1 through 42, of the matrix is circularly shifted upward by its column index (i.e. column 1 is circularly shifted by one position, column 2 by two positions, etc.) and if the Q-PARITY values are appended to the ends of the rows of the shifted matrix, the result is a matrix 310' shown in FIG. 4. This matrix represents the Q PARITY values as being calculated from data values taken along the rows of the shifted matrix. This representation defines the data values used to calculate the Q series.
As described above for the P codes, a set of syndromes, SQ(j), are generated, one for each row, j, of the matrix 310' by multiplying a vector of values vQ(j), taken along the row j of the shifted matrix 310', by the parity check matrix HQ. This operation is illustrated by equation (4). EQU SQ(j)=HQ.times.VQ(j) (4)
A conventional system for recovering data from a CD-ROM including a CIRS decoding system is shown in FIG. 5 (prior art). This is but one of many possible hardware implementations of a CIRS decoding system. It includes a microcontroller 510 which is connected by a system bus 520 to a random access memory (RAM) 512, a P decoder circuit 514, a Q decoder circuit 516 and CD-ROM controller 522. The controller 522 is connected, in turn, to a CD-ROM drive 524. Sectors are read from the CD-ROM drive 524 by the CD-ROM controller responsive to commands issued by the microcontroller 510. Each sector is written into memory and sequentially decoded using the P and Q decoder circuits 514 and 516.
The method used to decode the sector data is shown in the flow-chart diagram of FIG. 6 (prior art). According to this method, responsive to commands from a microprocessor 510, each data sector is read from the CD-ROM reader 524 via the controller 522 and stored into a random-access memory (RAM) 512. The data in the sector is demodulated and deinterleaved by the CD-ROM controller before it is written into the RAM 512.
The microprocessor 510 then directs the MSB plane of the header and user data contained in the sector to a P decoder 514. As described above with reference to Equations (1) and (2), the P decoder at step 610 of the process shown in FIG. 6, multiplies the parity check matrix HP by vectors VP(i) each corresponding to a respective p sequence having address values which correspond to the columns of the matrix 310 shown in FIG. 3. Each of the sequences VP(i) includes the P PARITY values but not the Q PARITY values in the column i of the matrix 310. The result of applying the MSB plane to generate a series of syndrome values, one for each column of the matrix.
As described above, if the value of the syndrome SP(i) is zero, it is assumed that there are no errors to correct in the header and user data values having the addresses indicated by column i of the matrix 310. A zero-valued syndrome may also be generated if the column of values has three or more single-bit errors. If the value of the syndrome is non-zero then there is either a one-bit error which can be detected and corrected or a multi-bit error, which can only be detected. The P decoder 514 at step 610 corrects any one-bit errors in the data and records any columns that have multiple errors that may be detected but not corrected.
Next, by step 612 of the method shown in FIG. 6, the microprocessor 510 passes the header and user data values to the Q decoder 516. As illustrated by step 612, and Equations (3) and (4), the Q decoder 516 applies the Q parity check matrix to each of the Q sequences and the corresponding Q parity values to produce a series of Q syndromes, SQ(j) one for each row j in the matrix 310', shown in FIG. 4.
As with the P-syndrome, a value of zero for the syndrome SQ(j) indicates no error in the corresponding sequence of Q values (i.e. row j of the matrix 310') or, possibly an undetectable error of three or more bits in the sequence of values. A non-zero syndrome value indicates a correctable error or a detectable error. The one-bit errors are corrected by the Q decoder 516 at step 612 of the method shown in FIG. 6. Also indications of any detected errors which cannot be corrected are saved and associated with the particular Q sequence from which the syndromes were generated.
At step 614 of the method, the microprocessor 10 checks the stored information on P errors and Q errors. If no uncorrectable errors were found in all of the P and Q sequences, then the method shown in FIG. 6 returns a value indicating that the decoder was successful and the MSB plane of the header and user data in the plane of the sector is marked as being error-free.
If, however, any of the P or Q sequences is marked as containing an error, then control is transferred to step 616 which increments an iteration count. At step 618, if the iteration count is less than a maximum number of allowed iterations, control is transferred to step 610 to recalculate the P-syndromes for each column of the matrix.
After repeating the P decoding and correction step 610, the Q decoding and correction step 612 is repeated. These decoding steps are repeated because an uncorrectable multi-bit error which was detected in the Q sequence may have been made correctable by the correction of an error in a common term of one or more of the Q sequences and vice-versa. The syndrome for each column and each diagonal of header and user data is recalculated to ensure that any zero-valued syndromes that may have represented three or more single-bit errors in one of the sequences are processed. If one or more of the errors was corrected during the evaluation of the other set of sequences, the syndrome may be non-zero when it is recalculated.
If, during any of the passes, no P sequence errors and no Q sequence errors are detected at step 614, the MSB plane is stored into the RAM 512 with an indication that it is error-free. If, however, an error in either the P sequence or the Q sequence exists after the maximum number of iterations through the data, the MSB data is stored in to the RAM 512 with an indication that it contains uncorrectable errors. The process described above is repeated for the LSB plane of data.
It is noted that the P decoder 514 and Q decoder 516 are separate and distinct hardware components. The number of operations which must be performed for each received CD-ROM sector make it impractical to implement these functions in software, running on the microcontroller 510.
The standard CIRS decoding algorithm described above, is linear in the number of passes over the matrix of header and user data values. There is, in general, no simple relationship between an arbitrary error pattern in the matrix and the number of passes N.sub.D needed to completely decode the data in the matrix. One estimate which may be used, however, is given by expectation (5). ##EQU3##
Where PEV indicates that the maximum operation is applied over all P-code error vectors and QEV indicates that the maximum operation is applied over all Q-code error vectors.
Exemplary times for executing this algorithm are given in Table 1. These times are normalized such that the amount of time used to calculate each syndrome of each sequence in the two sets is represented by a value of unity.
TABLE 1 ______________________________________ Errors 0 1 2 4 8 12 Iterations 1 1 2 3 4 5 Normalized 1.00 1.00 1.91 2.88 3.84 4.79 Execution Time ______________________________________
The results of tests performed by the inventor confirm that the decoding method described above is approximately linear in the number of times that the P sequences and Q sequences are processed.